package leetcode.backtrace;

import java.util.Stack;

/**
 * 
 * 给定一个包含了一些 0 和 1 的非空二维数组 grid 。

一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为 0 。)

 

示例 1:

[[0,0,1,0,0,0,0,1,0,0,0,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,1,1,0,1,0,0,0,0,0,0,0,0],
 [0,1,0,0,1,1,0,0,1,0,1,0,0],
 [0,1,0,0,1,1,0,0,1,1,1,0,0],
 [0,0,0,0,0,0,0,0,0,0,1,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,0,0,0,0,0,0,1,1,0,0,0,0]]
对于上面这个给定矩阵应返回 6。注意答案不应该是 11 ，因为岛屿只能包含水平或垂直的四个方向的 1 。

示例 2:

[[0,0,0,0,0,0,0,0]]
对于上面这个给定的矩阵, 返回 0。

 

注意: 给定的矩阵grid 的长度和宽度都不超过 50。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/max-area-of-island
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * 
 * @author 26233
 *
 *
 * 解法：
 * 	1、如果grid[i][j] = 1, 则i,j处的面积S(i,j) = 1 + S(i-1, j)
 * 	+ S(i+1, j) + S(i, j - 1) + S(i, j+1)
 * 	2、如果grid[i][j] = 0, 则S(i,j) = 0
 * 	3、在递归计算中，会出现重复计算S(x, y)的情况，使用辅助数组来记录已被访问过的元素位置
 * 
 * 
 */

public class LeetCode695_MaxAreaOfIsland {
	
	public static int maxAreaOfIsland(int[][] grid) {
		int[][] zero = new int[grid.length][grid[0].length];
		int max = 0;
		for(int i = 0; i < grid.length; i++) {
			for(int j = 0; j < grid[0].length; j++) {
				int tempArea = area(i, j, grid, zero);
				if(tempArea > max) max = tempArea;
			}
		}
		return max;
    }
	
	public static int area(int i, int j, int[][] grid, int[][] zero) {
		if(i >= grid.length || j >= grid[0].length || i < 0 || j < 0
				|| grid[i][j] == 0 || zero[i][j] == 1) return 0;
		zero[i][j] = 1;
		return 1 + area(i - 1, j, grid, zero) + area(i, j - 1, grid, zero) + area(i + 1, j, grid, zero) + area(i, j + 1, grid, zero);
	}
	
	// dfs + statck
	public static int maxAreaOfIsland2(int[][] grid) {
		int[][] zero = new int[grid.length][grid[0].length];
		Stack<Integer[]> noNavi = new Stack<>();
		int max = 0;
		int tempData;
		for(int i = 0; i < grid.length; i++) {
			for(int j = 0; j < grid[0].length; j++) {
				tempData = 0;
				if(grid[i][j] == 1) {
					zero[i][j] = 1;
					tempData++;
					addToStack(noNavi, i, j);
					while(!noNavi.empty()) {
						Integer[] tempPosition = noNavi.pop();
						if(tempPosition[0] < 0 || tempPosition[0] >= grid.length
								|| tempPosition[1] < 0 || tempPosition[1] >= grid[0].length
								|| grid[tempPosition[0]][tempPosition[1]] == 0
								|| zero[tempPosition[0]][tempPosition[1]] == 1) {
							continue;
						}
						zero[tempPosition[0]][tempPosition[1]] = 1;
						tempData++;
						addToStack(noNavi, tempPosition[0], tempPosition[1]);
					}
				}
				max = max > tempData ? max : tempData;
			}
		}
		return max;
    }
	
	public static void addToStack(Stack<Integer[]> stack, int i, int j) {
		stack.add(new Integer[] {i - 1, j});
		stack.add(new Integer[] {i + 1, j});
		stack.add(new Integer[] {i, j - 1});
		stack.add(new Integer[] {i, j + 1});
	}
	
	public static void main(String[] args) {
		int[][] data = {{0,0,1,0,0,0,0,1,0,0,0,0,0},
		                {0,0,0,0,0,0,0,1,1,1,0,0,0},
		                {0,1,1,0,1,0,0,0,0,0,0,0,0},
		                {0,1,0,0,1,1,0,0,1,0,1,0,0},
		                {0,1,0,0,1,1,0,0,1,1,1,0,0},
		                {0,0,0,0,0,0,0,0,0,0,1,0,0},
		                {0,0,0,0,0,0,0,1,1,1,0,0,0},
		                {0,0,0,0,0,0,0,1,1,0,0,0,0}};
		
		int[][] data2 = 
				{{0,0,1,0,0,0,},
                {0,0,0,0,0,0,},
                {0,1,1,0,1,0,},
                {0,1,0,0,1,1,},
                {0,1,0,0,1,1,},
                {0,0,0,0,0,0,},
                {0,0,0,0,0,0,},
                {0,0,0,0,0,0,}};
		int[][] data3 = {{1}};
		System.out.println(data.length);
		// int r = maxAreaOfIsland(data3);
		int r = maxAreaOfIsland2(data2);
		System.out.println("area = " + r);
	}

}
